class Solution {
    public:
        ListNode* rotateRight(ListNode* head, int k) {
            //没有或者有一个节点的情况直接返回
            if(head == nullptr || head->next == nullptr)
                return head;
    
            //遍历查看有多少个节点
            int count_node = 0;
            ListNode* node = head;
            while(node != nullptr)
            {
                count_node++;
                node = node->next;
            }
    
            //计算出要找的第一个节点位置
            count_node = k % count_node;
            //如果是0，那么代表正好移动回原来的顺序
            if(count_node == 0)
            {
                return head;
            }
    
            //找到倒数第k + 1的位置 和 结尾的位置
            ListNode* prev = head;
            ListNode* cur = head;
            for(int i = 0; i < count_node; i++)
            {
                cur = cur->next;
            }
            //同时移动
            while(cur->next != nullptr)
            {
                cur = cur->next;
                prev = prev->next;
            }
            //重新组合顺序
            cur->next = head;
            head = prev->next;
            prev->next = nullptr;
            
            return head;
        }
    };